#!/usr/bin/python

import os, sys, readline
histfile = os.path.join(os.environ["HOME"], ".%shist"%os.path.basename(sys.argv[0]))
try:
    readline.read_history_file(histfile)
except IOError:
    pass
import atexit
atexit.register(readline.write_history_file, histfile)

modul = 32 
if len(sys.argv) > 1:
    modul = int(sys.argv[1])

def ServiceStringToBin(ss):
    paths  = [":".join(ss.split(":")[:item+1]) for item in range(len(ss.split(":")))]
    hashes = [hash(item) % modul for item in paths]
    #print zip(paths, hashes)
    return tuple(sorted(set(hashes)))

all_bin = set()
collided = set()
all_services = set()
try:
    while True:
	service = raw_input("service string: ")
	bin = ServiceStringToBin(service)
	print "%-35s\t"%service, bin 
	if bin in all_bin:
	    collided.add(bin)
	all_bin.add(bin)
	all_services.add((service, bin))
except KeyboardInterrupt:
    print
except EOFError:
    print

print "collisions: %.2f%%"%(100 * len(collided) / float(len(all_services))) + 5*"\t-*-"
for service, bin in all_services:
    if bin in collided:
        print "%30s\t"%service, bin

# SAGE: Wahrscheinlichkeit keine kollision zu haben   
# bit = 32
# items = 4
# services = 30
# elements = bit ** items
# prob = factorial(elements) / factorial(elements - services) / (elements)**services
# float(prob)

